Теорема о графе блоков

Граф блоков $B(G)$ графа $G$ определяется следующим образом: вершинами являются блоки и точки сочленения $G$; каждая точка сочленения соединена неориентированным ребром со всеми блоками, в которые она входит.

Граф блоков связного графа $G$ является деревом.

$B(G)$ очевидно связен; докажем, что в $B(G)$ нет циклов. Пусть имеется цикл $B_1, a_1, \dots, B_k, a_k, B_1$ ($k \ge 2$). Тогда любые вершины из блоков, например, $B_1$ и $B_k$ соединены двумя путями (один проходит через $a_k$, а другой — нет). Следовательно, $a_k$ не точка сочленения по лемме о точке сочленения. $\square$